package com.lans.SortAlgorithm;

import java.util.ArrayList;
import java.util.Arrays;

/*
 * @author: lans
 * @date: 2024/12/22
 * @name: 刘宇
 * 基数排序
 */
//基数排序
public class BasicSort {
    private static final int[] array1 = {53,3,542,728,14,214};
    public static int[] sort(int[] array){
        //1.先找出最大值
        int max = 0;
        for(int temp:array){
            if(temp>max){
                max=temp;
            }
        }
        //2.计算最大值是几位数
        int maxDigit = 0;
        while(max!=0){
            max/=10;
            maxDigit++;
        }
        //3.创建0-9个桶
        ArrayList<ArrayList<Integer>> buckets = new ArrayList<>();
        for(int i=0;i<10;i++){
            buckets.add(new ArrayList<>());
        }
        //第一次取个位数 然后十位 百位...
        int mold = 10;
        int div=1;
        //控制一共取多少位数
        //如153取出个位153%10=53/1=3 53取出个位%10/1=3 3取出个位%10/1=3
        //153取十位 153%100=53/10=5 53取出十位%100=53/10=3 3取出十位3%100=3/10=0
        for(int i=0;i<maxDigit;i++,mold*=10,div*=10){//每一次循环代表取个位 十位 ...

            for (int k : array) {
                int num = (k % mold) / div;
                buckets.get(num).add(k);//将对应元素放入桶中
            }
            //所有的取出放桶已完成 按序取出即是排序顺序
            int index=0;
            for (ArrayList<Integer> list : buckets) {//遍历桶集合
                for (Integer integer : list) {//遍历集合中的元素
                    array[index++] = integer;//存入数组
                }
                list.clear();//清空桶
            }
        }
        return array;
    }

    public static void main(String[] args) {
        int[] array11 = sort(array1);
        System.out.println(Arrays.toString(array11));
    }
}
